//
//  518. 零钱兑换II.swift
//  LeetCodeTrain
//
//  Created by mojiit on 2021/6/15.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation

class Solution518 {
    // 零钱兑换ii
    // 定义dp[j] 表示凑成金额j的货币组合数为dp[j]
    // 递推公式 dp[j] += dp[j - coins[i]]
    func change2(_ amount: Int, _ coins: [Int]) -> Int {
        var dp = Array(repeating: 0, count: amount + 1)
        dp[0] = 1
        for i in 0..<coins.count {
            if amount < coins[i] {
                break
            }
            for j in coins[i]...amount {
                dp[j] += dp[j - coins[i]]
            }
        }
        return dp[amount]
    }
    
    static func test() {
        let coins = [1, 2, 5]
        let amount = 5
        let solution = Solution518()
        let result = solution.change2(amount, coins)
        print(result)
    }
}
